package com.linc.ds.heap;

import java.util.Arrays;

public class MaxHeap<E extends Comparable<E>> {
  private static final int SIZE = 8;
  private final Object[] data;
  private final int size;
  private int curr;

  public MaxHeap(int size) {
    this.size = size;
    curr = 0;
    data = new Object[size];
  }

  public MaxHeap() {
    this(MaxHeap.SIZE);
  }

  private void swap(int i, int j) {
    Object temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }

  @SuppressWarnings("unchecked")
  public <T extends E> boolean add(T e) {
    if (curr == size) return false;
    data[curr] = e;

    int index = curr;
    while (index != 0) {
      int parent = (index - 1) / 2;
      if (((E) data[index]).compareTo(((E) data[parent])) > 0) {
        swap(index, parent);
        index = parent;
      } else {
        break;
      }
    }
    curr++;
    return true;
  }

  @SuppressWarnings("unchecked")
  public E remove() {
    if (curr == 0) return null;
    curr--;
    E r = (E) data[0];
    data[0] = data[curr];
    int index = 0;
    while (true) {
      int right = ((index + 1) << 1);
      int left = right - 1;
      if (left >= curr) {
        break;
      }
      if (right >= curr) {
        if (((E) data[index]).compareTo((E) data[left]) < 0) {
          swap(index, left);
        }
        break;
      }
      int max = ((E) data[left]).compareTo((E) data[right]) > 0 ? left : right;
      if ((((E) data[index]).compareTo((E) data[max])) < 0) {
        swap(index, max);
        index = max;
      } else {
        break;
      }
    }
    return r;
  }

  public boolean isEmpty() {
    return curr == 0;
  }

  @Override
  public String toString() {
    return "Heap{" + "data=" + Arrays.toString(data) + ", size=" + size + ", curr=" + curr + '}';
  }
}
